package algorithms.leaning.class12;

import common.bean.TreeNode;

/**
 * 给定一棵二叉树的头节点head, 返回这颗二叉树中最大的二叉搜索子树的大小
 * 有可能自己就是搜索二叉树
 * 也有可能子树是搜索二叉树
 *
 * @author guichang
 * @date 2021/6/12
 */

@SuppressWarnings("all")
public class Code6_二叉树_最大二叉搜索子树大小 {
    // 1、x做头
    //    左右子树是不是BST
    //    左树最大值、右树最小值
    //    左右树的size
    // 2、x不做头
    //    左右最大BST的size

    public static int maxBSTSize(TreeNode node) {
        return process(node).maxBSTSize;
    }

    private static Info process(TreeNode node) {
        if (node == null) {
            return new Info(0, 0, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }

        Info tl = process(node.left);
        Info tr = process(node.right);

        int max = Math.max(Math.max(tl.max, tr.max), node.val);
        int min = Math.min(Math.min(tl.min, tr.min), node.val);
        int size = tl.size + tr.size + 1;
        // x不做头的情况
        int maxBSTSize = Math.max(tl.maxBSTSize, tr.maxBSTSize);
        // x做头的情况，左右都是BST且左树最大值小于x，右树最小值大于x
        boolean leftBST = tl.max == tl.maxBSTSize;
        boolean rightBST = tr.max == tr.maxBSTSize;
        if (leftBST && rightBST && tl.max < node.val && tr.min > node.val) {
            maxBSTSize = Math.max(maxBSTSize, size);
        }
        return new Info(maxBSTSize, size, max, min);

    }

    private static class Info {
        int maxBSTSize; // 最大搜索子树的大小
        int size; // 自己的大小
        int max; // 自己的最大值
        int min; // 自己的最小值

        public Info(int maxBSTSize, int size, int max, int min) {
            this.maxBSTSize = maxBSTSize;
            this.size = size;
            this.max = max;
            this.min = min;
        }
    }
}